package 剑指offer;

public class 剑指Offer33二叉搜索树的后序遍历序列 {
    public static void main(String[] args) {
        剑指Offer33二叉搜索树的后序遍历序列 o = new 剑指Offer33二叉搜索树的后序遍历序列();
        System.out.println(o.verifyPostorder(new int[]{1,2,5,10,6,9,4,3}));
    }

    public boolean verifyPostorder(int[] postorder) {
        //如果数组长度= 1 || = 0，那么她一定是
        if (postorder.length < 3) return true;
        //否则存在多个数，我只需要判断从当前根节点出发，是否满足后续遍历
//        return verifyPostorderHelp() && verifyPostorder()
        return verifyPostorderHelp(postorder,0,postorder.length - 1);
    }

    private boolean verifyPostorderHelp(int[] postorder, int left, int right) {
        if (left >= right) return true;//如果拆分到只有一个元素，那么肯定是后续遍历的结果
        int pos = left;
        while(postorder[pos] < postorder[right]) pos++;
        int sit = pos;
        while(postorder[pos] > postorder[right]) pos++;
        return pos == right && verifyPostorderHelp(postorder,left,sit-1) && verifyPostorderHelp(postorder,sit,right-1);
    }
}
